package com.dataStructure.array;

import java.io.CharArrayReader;
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.function.Predicate;


/**
 *  关于数组二分查找 while(left <= right)的一些总结：这里的right 和 left为索引
 *  1.对于无重复元素的二分查找类型，假设没有查找到结果 最后一定是right + 1 = left,
 *     而且会有right的一侧是小于目标值的，left是大于目标值的一侧，此乃真理也
 *
 *  2.对于含有重复元素的区间二分查找：
 *
 *
 * 数组的移除元素：在移动元素位置时，j < size -1，不然数组下标超出限制
 *
 * 双指针法移除元素: 相当于两个快慢指针，快指针去寻找目标值，如果没找到，快指针，慢指针向前移动一位，并将慢指针指向的值
 * 设置为快指针的值。      否则快指针找到目标值，移动快指针，满指针不动。
 * 最后慢指针的小标一定是删完数组的下一位
 *
 *
 * 滑动窗口思想：当出现需要找出数组某个子数组满足某个条件时，那个子数组就是我们要找的窗口，
 * 所谓窗口，就一定会有起点和终点，当开始寻找搜索窗口时，终点不断移动，直到找到合适的子数组时，这时，便可以移动数组的起点，直到不满足条件
 */

public class LeetCode {

    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<>();
        list.removeIf(integer -> integer > 10);

    }

    /**
     * 974. 和可被 K 整除的子数组
     */
    public int subarraysDivByK(int[] nums, int k) {

        return 0;
    }

    /**
     * 149 ，统计优美子数组
     */
    public int numberOfSubarrays(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int ct = 0;
        int[] sums = new int[nums.length + 1];
        sums[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            //如果是偶数就是0，奇数则为1
            int j = nums[i] % 2;
            sums[i + 1] = sums[i] + j;

        }
        System.out.println(Arrays.toString(sums));
        // sums[i , j] = sums[j + 1] - sums[i]
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(sums[i ] - k)) {
                ct += map.get(sums[i] - k);
            }
            map.putIfAbsent(sums[i] - k, 0);
            map.put(sums[i] - k, map.get(sums[i] - k ) + 1);
        }

        return ct;

    }
    /**
     *
     * 和为k的子数组
     * 前缀和思想
     *
     * sum[i] = ar[i] + sum[i - 1]
     *
     * sumLR[i,j] = sum[j] - sum[i - 1]
     */
    public int subarraySum2(int[] nums, int k) {
        int[] sum = new int[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap<>();
        int ct = 0;
        sum[0] = 0;
        map.put(sum[0], 1);
        for (int i = 1 ; i < nums.length; i++) {
            sum[i] = nums[i - 1] + sum[i - 1];
            map.putIfAbsent(sum[i], 0);
            map.put(sum[i], map.get(sum[i]) + 1);
        }
        System.out.println(map);
        System.out.println(Arrays.toString(sum));
        for (int i = 0; i < nums.length ;i++) {
            Integer LR = map.get(sum[i] - k);
            if (LR != null) {
                ct += LR;
            }
        }
        return ct;

    }

    /**
     * 和为k的子数组
     * 这是滑动窗口做法，因为有负数和0的存在，所以不可取
     */
    public int subarraySum(int[] nums, int k) {
        int slow = 0;
        int sum = 0;
        int ct = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            sum += nums[fast];
            while (sum >= k) {
                if (sum == k) {
                   ct++;
                   sum -= nums[slow];
                   slow++;
                }
                else {
                    sum -= nums[slow];
                    slow++;
                }
            }
        }
        return ct;
    }

    /**
     * 螺旋矩阵
     */
    public int[][] generateMatrix(int n) {
        int total = n * n;
        int[][] ar = new int[n][n];
        boolean[][] visited =new boolean[n][n];
        int row = 0; int column = 0;

        int[][] index = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int curIndex = 0;

        for (int i = 1 ; i <= total; i++) {
            ar[row][column] = i * i;

            int nextRow = row + index[curIndex][0];
            int nextColumn = row + index[curIndex][1];

            if (nextRow > n || nextRow < 0 || nextColumn > n|| nextColumn < 0 ||
                    visited[nextRow][nextColumn]) {
                curIndex = (curIndex + 1) % 4;
             }
            row = row + index[curIndex][0];
            column += index[curIndex][1];
        }
        return ar;
    }

    /**
     * 螺旋矩阵-2 59
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        int[][] index = new int[][] {{0,1}, {1, 0}, {0, -1}, {-1, 0}};
        int row = 0;
        int column = 0;
        int fanxiang = 0;
        for (int i = 0; i < matrix.length * matrix[0].length; i++) {
            list.add(matrix[row][column]);

            int nextRow = row + index[fanxiang][0];
            int nextColumn = column +  index[fanxiang][1];
            visited[row][column] = true;
            //该转弯了
            if (nextRow < 0 || nextRow >= matrix.length || nextColumn <0 || nextColumn >= matrix[0].length || visited[nextRow][nextColumn] ){
                fanxiang = (fanxiang + 1) % 4;
            }

            row += index[fanxiang][0];
            column += index[fanxiang][1];
        }

        return list;

    }


    /**
     *
     剑指 Offer 57 - II. 和为s的连续正数序列
     */
    public int[][] findContinuousSequence(int target) {
        ArrayList<int[]> list = new ArrayList<>();
        int slow = 1;
        int sum = 0;
        for (int fast = 1 ; fast < target; fast++) {
            sum += fast;
            while (sum >= target) {
                if (sum == target) {
                    int[] ar = new int[fast - slow + 1];
                    for (int i = 0; i <fast - slow + 1; i++) {
                        ar[i] = slow + i;
                    }
                    list.add(ar);
                    sum -= slow;
                    slow++;

                } else {
                    sum -= slow;
                    slow ++;
                }
            }
        }
        return list.toArray(new int[0][]);
    }

    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }


     



        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1;i <= n; i++) {
            if(!set.contains(i)) {
                list.add(i);
            }
        }

        return list;
    }


    /**
     * 无重复的最长字串
        力扣 3
     */
    public int lengthOfLongestSubstring(String s) {
        char[] ar = s.toCharArray();
        int i = 0 ;
        int j = 0;
        int maxLength = 0;
        Set<Character> set = new HashSet<>();
        for (j = 0; j < ar.length; j++) {
            if (!set.contains(ar[j])) {
                set.add(ar[j]);
                continue;
            }

            while(set.contains(ar[j])) {
                int curLength = j - i +1;
                maxLength = Math.max(maxLength, curLength);
                set.remove(ar[i]);
                i++;
            }
        }

        return maxLength;

    }


    /**
     *   数组的第k最大元素
     */
    public int findKthLargest(int[] nums, int k) {
//        TreeSet<Integer> set = new TreeSet<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2 - o1;
//            }
//        });
//        for (int i = 0; i < nums.length; i++) {
//            set.add(nums[i]);
//        }
//        int i = 0;
//        for (Integer e : set) {
//            if (i == k -1) {
//                return e;
//            }
//            i++;
//        }
//        return 0;

        Arrays.sort(nums);
        return nums[nums.length - k];
    }


    public String minWindow(String s, String t) {
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();

        HashMap<Character,Integer> tMap = new HashMap<>();
        for (char e : tChar) {
            if (tMap.containsKey(e))
                tMap.put(e,tMap.get(e) + 1);
            else
                tMap.put(e,0);
        }
        HashMap<Character, Integer> sMap = new HashMap<>();
        int i = 0;
        int result = Integer.MAX_VALUE;
        String result2 = "";
        for (int j = 0 ; j < sChar.length; j++) {
            if (sMap.containsKey(sChar[j]))
                sMap.put(sChar[j],sMap.get(sChar[j]) + 1);
            else
                sMap.put(sChar[j],0);

            while (compare(tChar,sMap,tMap)) {
                int length = j - i +1;
                if (length < result) {
                  ;
                }
                //删除第一位
                if (sMap.get(sChar[i]) >= 1) {
                    sMap.put(sChar[i],sMap.get(sChar[j]) -1);
                }
                else
                    sMap.remove(sChar[i]);
                i++;
            }

        }
        return  null;


    }



    public static boolean compare(char[] chars,HashMap<Character,Integer> sMap,HashMap<Character,Integer> tMap) {
        for (char e : chars) {
            if (tMap.get(e) > (sMap.get(e))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 904 水果成篮   滑动窗口算法
     */
    public static int totalFruit(int[] fruits) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int i = 0;
        int maxLength = Integer.MIN_VALUE;
        int curLength = 0;
        for (int j = 0 ;j < fruits.length;j++) {
            //将水果放入篮子
            if (map.get(fruits[j]) != null) {
                map.put(fruits[j],map.get(fruits[j]) +1);
            } else {
                map.put(fruits[j],1);
            } //放入完成

            //篮子超出了

            while (map.size() > 2) {
                map.put(fruits[i],map.get(fruits[i]) -1);
                if(map.get(fruits[i]) == 0) {
                    map.remove(fruits[i]);
                }

                i++;
            }
            curLength = j -i +1;
            if (curLength > maxLength) {
                maxLength = curLength;
            }
        }


        return maxLength == Integer.MIN_VALUE ? 0 : maxLength;

    }




    /**
     *  力扣209 滑动窗口思想，长度最小的子数组 ,
     *
     */

    public int minSubArrayLen2(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int curLength = 0;
        int i = 0;
        int sum = 0;
        //滑动窗口的终止位置
        for (int j = 0; j < nums.length;j++) {
            sum += nums[j];
            while (sum >= target) {
                //记录当前滑动窗口的总长度
                curLength = j - i +1;
                minLength = Integer.min(curLength,minLength);
                sum -= nums[i];
                i ++;
            }
        }

        return minLength;

    }

    /**
     * 力扣 209 暴力解法会超时，
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int historyLength = 0;
        int recordLength = 0;
        int total = 0;
        int firstflag = 0;
        for (int i = 0;i < nums.length; i++) {
            for (int j = i; j < nums.length;j++) {
                recordLength++;
                total += nums[j];
                if (total >= target) {
                    if (historyLength < recordLength) {
                        if (firstflag == 0 ){
                            firstflag = 1;
                            historyLength = recordLength;
                        }
                        total = 0;
                        recordLength = 0;
                    } else {
                        historyLength = recordLength;
                        total =0;
                        recordLength = 0;
                    }
                }
            }
            total =0;
            recordLength =0;
        }
        return historyLength;
    }

    /**
     * 力扣844：比较含退格的字符串, 利用栈的思想进行匹配退格符
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare(String s, String t) {
        StringBuilder s1 = new StringBuilder();
        StringBuilder t1 = new StringBuilder();
        for (char e : s.toCharArray()) {
            if (e != '#') {
                s1.append(e);
            }
            else if (s1.length() > 0) {
                s1.deleteCharAt(s1.length() -1);
            }
        }
        //
        for (char e : t.toCharArray()) {
            if (e != '#') {
                t1.append(e);
            }
            else if (s1.length() > 0) {
                t1.deleteCharAt(s1.length() -1);
            }
        }
        return s1.toString().equals(t1.toString());

    }

    /**
     * 力扣283 移动零
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int slowIndex = 0;
        for (int fastIndex = 0 ; fastIndex < nums.length; fastIndex++ ) {
            if (nums[fastIndex] != 0) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }

        for (int i = slowIndex ; i < nums.length;i++) {
            nums[i] = 0;
        }
    }

    /**
     * 力扣26 优化，双指针法，通过快慢指针，只需一个for循环便可以删除数组元素，而不用像传统方法两层for循环先便利找出目标值，
     * 再遍历删除
     * 快慢指针的做法：两个指针一开始指向同一个位置，只要不满足删除的条件便同时进位，双指针遍历完后的一些结论
     * slowIndex 删除了几个元素，slowIndex指向倒数第几位（也就是之前的都是删除目标值的一个数组片段）
     * @param nums
     * @return
     */
    public int removeDuplicates2(int[] nums) {

        int slowIndex = 1;

        for (int fastIndex = 1;fastIndex < nums.length;fastIndex++) {
                if (nums[fastIndex] != nums[fastIndex-1]) {
                    nums[slowIndex] = nums[fastIndex];
                    slowIndex++;
                }
        }

        return slowIndex;
    }
    /**
     * 力扣26， 删除有序数组的重复项
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int pre = 0;
        int cur;
        int size = nums.length;
        for (int i = 0; i < size ;i++) {

            cur = nums[i];
            if (i == 0 && cur == 0) {
                continue;
            }
            if (pre == cur) {
                //删除重复元素
                for (int j = i ; j < size-1; j++) {
                    nums[j] = nums[j+1];
                }
                i--;
                size--;
            } else {
                pre = nums[i];
            }
        }

        return size;
    }

    /**
     * 力扣27. 移除元素
     * i--,是因为移除元素后，每一位都向前移动一个位置
     * 为了解决联讯元素的出现
     */
    public static int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) {
                //开始移动元素位置，发现目标元素的位置为 i
                for (int j = i ;j < size-1 ;j++) {
                    nums[j] = nums[j+1];
                }
                i--;
                size--;
            }

        }
        return size;
    }

    /**
     * 力扣369 ，完全平方数
     * @param num
     * @return
     */
    public static boolean isPerfectSquare(int num) {
        int left = 1;
        int right = num;
        while (left <= right) {
            int mid = (left + right) /2;
            if (1.0 * num / mid  < mid) {
                right = mid -1;
            } else if (1.0 * num / mid  > mid) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 力扣69 正解
     * @param x
     * @return
     */
    public int mySqrt2(int x) {
        int left = 0;
        int right = x;
        if (x ==0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }
        while (left <= right) {
            int mid = (left + right) /2;
            if (x / mid < mid) {
                right = mid -1;
            } else if (x /mid > mid) {
                left = mid +1;
            } else {
                return mid;
            }
        }
        return right;
    }

    /**
     * 力扣69 暴力会超时
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        int value = 0;
        for (int i = 0;i <= x; i++) {
           if (i * i  == x) {
               value = i;
               break;
           } else if (i * i > x) {
               value = i-1;
               break;
           }
           else {
               continue;
           }

        }
        return value;
    }

    /**
     * 力扣 34
     * @param nums
     * @param target
     * @return
     */
    public static int[] search2(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
        // 情况二
        return new int[]{-1, -1};
    }

    static int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    static  int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }


    /**
     *  力扣 704
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;
        while (left <= right) {
            int mid = (left  + right) /2;
            if (target > nums[mid]) {
                left = mid + 1;
            }
            else if(target < nums[mid]) {
                right = mid -1;
            }
            else
                return mid;
        }
        return -1;
    }
//    搜索插入位置
    private static int searchInsert2(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1;

        while(left <= right) {

            int mid = (left + right)/2;
            if (target > nums[mid]) {
                left =  mid +1;
            } else if (target < nums[mid]) {
                right = mid -1;
            }
            else
                return mid;
        }
        return right+1;
    }


    //    搜索插入位置 1,3,5,8
    public static int searchInsert(int[] nums, int target) {
        int leftNode = 0;
        int rightNode = nums.length -1;
        int i = binarySearch(nums, leftNode, rightNode,target);
        return i;
    }

    private static int binarySearch(int[] nums, int leftNode, int rightNode,int target) {
        if (leftNode  == rightNode) {
            return -1;
        }
        int index = (leftNode + rightNode) / 2;
        if (target > nums[index]) {
            leftNode = index;
            return binarySearch(nums,leftNode,rightNode,target);
        }
        else if (target < nums[index]) {
            rightNode = index;
            return binarySearch(nums,leftNode,rightNode,target);
        }
        else {
            return index;
        }

    }



    //    寻找数组中心索引
    //前缀和思想，我们知道，当数组遍历到第i个元素时，其 sum右 = total - sum左 - nums[i],由左右元素相等
    //得：total - sum左 - nums[i] == sum左
    //化简得：2sum左 = total - nums[i]
    public static int pivotIndex2(int[] nums) {
        int total = Arrays.stream(nums).sum();
        int sumLeft = 0;
        for (int i = 0; i < nums.length; i++) {
            if (2 * sumLeft + nums[i] == total) {
                return i;
            }
            sumLeft += nums[i];
        }

        return -1;
    }


//    此法用于直接暴力遍历，先算左边，再算右边
    public static int pivotIndex(int[] nums) {
        int leftSum = 0;
        int rightSum = 0;
        int end = -1;
        for (int i = 0;i < nums.length; i++) {
            if (i == 0) {
                end = equal(nums,rightSum);
            } else {
                end = equal2(i,nums,leftSum,rightSum);

            }
            if (end != -1) {
                return end;
            }
        }

        return end;
    }

    private static int equal2(int index, int[] nums, int leftSum, int rightSum) {
//
        //算左边总和
        for (int i = 0;i < index ; i++) {
            leftSum += nums[i];
        }

        for (int j = index+1 ;j < nums.length;j++) {
            rightSum += nums[j];
        }

        return leftSum == rightSum ? index : -1;


    }

    private static int equal(int[] nums,int rightSum) {
        for (int i = 1; i < nums.length; i++) {
            rightSum += nums[i];
        }
        return rightSum == 0 ? 0 : -1;
    }

}
